1. Technical Field
The present invention relates generally to electrical computers and digital processing systems having processing architectures and performing instruction processing, and more particularly to processes for multiplication that can be implemented in such.
2. Background Art
Many modern computerized processes employ complex mathematics, wherein the calculations are actually performed mostly with just a few fundamental operations. Two particular such fundamental operations are of present interest, adding and multiplying values. Multiplication can be performed as a series of additions, but it usually is more efficient to use just a few addition operations combined with other fundamental operations like bit-wise shifts. For this reason, it is therefore often best to regard addition and multiplication separately when used in computerized processes.
Optimizing computerized processes is important to improve applications in which the processes are already used, as well as to permitting new applications to emerge. Optimizing computerized processes is an ongoing quest that can be accomplished by optimizing the hardware or the algorithms performing the processes, or both.
Digital signal processing (DSP) is a computerized process that is widely used in modern electronic communications, and that serves very well as an example here. When performing DSP, it is desirable that overall speed and efficiency be optimized. An appreciation of the underlying mathematics used in the DSP is important for accomplishing this.
The mathematical term “transform” refers to a very powerful technique used for analyzing certain types of integral or differential equations, in particular including those describing linear time invariant systems. The concept to the transform traces its roots to the functional analysis branch of mathematics, which primarily deals with the study of spaces of functions in which a particular function has another function as its argument. The transform of one or more integral or differential equations can employ a mapping technique where an original equation or equations that are represented in a time dependent domain are transformed into a complex domain. The result of this often leads to a more solvable set of equations than the original equations and, upon finding the solution in the complex domain, an inverse transform can be performed to map the solution back to the time dependent domain. A general form of an integral transform can be defined as:
                              g          ⁡                      (            α            )                          =                              ∫            a            b                    ⁢                                    f              ⁡                              (                t                )                                      ⁢                          K              ⁡                              (                                  α                  ,                  t                                )                                      ⁢                          ⅆ              t                                                          (        1        )            where K(α,t) is often referred to as the Integral Kernel of the transform. The class of integral equations described by equation (1) has a broad practical application into areas such as electrical circuits, harmonic oscillators, optical devices, mechanical systems, signal processing, and many others.
The Laplace Transform L{ƒ(t)} is a subset of the class of transforms defined by equation (1) and is defined as a function of the variable s where the limits of integration and the integral kernel are redefined from equation (1) as a=0, b=∞, and K(α,t)=e−st:
                              L          ⁢                      {                          f              ⁡                              (                t                )                                      }                          =                              ∫            0            ∞                    ⁢                                    f              ⁡                              (                t                )                                      ⁢                          ⅇ                              -                st                                      ⁢                                                  ⁢                                          ⅆ                t                            .                                                          (        2        )            The use of a laplace transform on ƒ(t) is only valid when s is sufficiently large and certain conditions are met. These conditions are flexible enough, however, to allow ƒ(t) to take on the functional form of nearly any useful function found in practice.
It is an all too common occurrence, unfortunately, that a certain function F(s) is not the transform of a single known function. On the other hand, F(s) can be represented as the product of two functions {circumflex over (ƒ)}(s) and ĝ(s), each of which is the result of the transform of a known function ƒ(t) and g(t), respectively:F(s)={circumflex over (ƒ)}(s)ĝ(s),  (3)wherein g(t) must satisfy the same conditions as ƒ(t). By understanding this link between F(s), ƒ(t), and g(t) the following holds:
                                          F            ⁡                          (              s              )                                =                      L            ⁢                          {                                                ∫                  0                  t                                ⁢                                                      f                    ⁡                                          (                                              t                        -                        τ                                            )                                                        ⁢                                      g                    ⁡                                          (                      τ                      )                                                        ⁢                                      ⅆ                    τ                                                              }                                      ,                            (        4        )            which is referred to as the Convolution Theorem.
At this point it should be noted that the convolution theorem results in a transformation of an integral of just one variable. The techniques for approximating an integral of just one variable therefore apply. Between the integral representation and a Riemann Sum representation for the convolution integral defined in equation (4), the following holds:
                                                        ∫              0              t                        ⁢                                          f                ⁡                                  (                                      t                    -                    τ                                    )                                            ⁢                              g                ⁡                                  (                  τ                  )                                            ⁢                              ⅆ                τ                                              =                                    lim                                                Δ                  ⁢                                                                          ⁢                  τ                                →                0                                      ⁢                                          ∑                                  k                  =                  0                                t                            ⁢                                                          ⁢                                                f                  ⁡                                      (                                          c                                              t                        -                        k                                                              )                                                  ⁢                                  g                  ⁡                                      (                                          c                      k                                        )                                                  ⁢                Δ                ⁢                                                                  ⁢                τ                                                    ,                            (        5        )            where each ct-k and ck are chosen arbitrarily in the kth subinterval. In practice the right hand side of the equality in equation (5) is approximated by utilizing a very small Δt and realizing there exists an error term of some order dependent on the numerical technique chosen and the value of Δt, this can be expressed as:
                                                        lim                                                Δ                  ⁢                                                                          ⁢                  τ                                →                0                                      ⁢                                          ∑                                  k                  =                  0                                t                            ⁢                                                          ⁢                                                f                  ⁡                                      (                                          c                                              t                        -                        k                                                              )                                                  ⁢                                  g                  ⁡                                      (                                          c                      k                                        )                                                  ⁢                Δ                ⁢                                                                  ⁢                τ                                              =                                                    ∑                                  k                  =                  0                                t                            ⁢                                                          ⁢                                                f                  ⁡                                      (                                          c                                              t                        -                        k                                                              )                                                  ⁢                                  g                  ⁡                                      (                                          c                      k                                        )                                                  ⁢                Δ                ⁢                                                                  ⁢                τ                                      +                          Ο              ⁡                              (                                  Δ                  ⁢                                                                          ⁢                                      τ                    m                                                  )                                                    ,                            (        7        )            where m is the order of accuracy that can be represented by the resultant sum. (The value of m also represents the number of digits of precision that can be expected.) Any numerical technique used to approximate the convolution integral will result in a large number of multiplications and additions, and it follows that speeding up the processes of multiplication and/or addition will result in a greater overall speed when performing the convolution method.
The use of convolution is a preferred method in the course of performing DSP, particularly where a digital filter is used to remove unwanted parts or to extract useful parts of a signal. Any desired filtering that can be expressed as a mathematical function can be achieved through the use of a digital filter to perform numerical calculations on sampled data values of a signal. The integral kernel previously described is essentially another name for the digital filter.
Finite impulse response (FIR) and infinite impulse response (IIR) are the two main types of digital filters that are used in DSP applications. The difference between an IIR and FIR filter is in the impulse response function that describes the filtering function. An IIR filter utilizes an impulse function which is non-zero over an infinite length of time, whereas an FIR filter utilizes an impulse function which will ultimately settle to zero over a finite time interval.
The more common of the two filter types is the FIR. This is mainly due to the fact that a FIR filter does not have internal feedback to the filter, like an IIR filter does. Such internal feedback can cause an IIR filter to respond indefinitely to an impulse. The advantage of a FIR filter is thus apparent by the word finite in the filter's name. The use of this word indicates that the impulse from the filter will ultimately settle to zero. This advantage of the FIR filter is apparent in another way; error does not propagate during an iterative summing process, meaning the error term will stay constant throughout the entire process. This is a distinct advantage over an IIR filter, where the error could potentially propagate for each additional iterative output sum.
A major drawback of digital filters today is that their speed is restricted by the speed of the processor hardware used, and if high filtering speeds are required the processor hardware can be very expensive. Digital filters have nonetheless become commonplace in almost every electronic communication device, as the cost of processing power has decreased immensely over the last few years. This has resulted in an industry wide unresponsiveness to reducing the computational costs associated with a DSP. This unresponsiveness cannot continue, however, as further increases in computational power are becoming increasingly difficult to achieve in conventional processor hardware.
Summarizing, first by reiterating: optimizing computerized processes is an ongoing quest that can be accomplished by optimizing the hardware or the algorithms performing the processes (or both). In computerized processes, multiplication is important and there will be welcome benefit if how multiplication is accomplished in such processes can be improved.